package com.caoyanan.algorithm.question.zuoTraining.training003.class07;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;

/**
 *
 * 给定一个无序数组arr，如果只能再一个子数组上排序
 * 返回如果让arr整体有序，需要排序的最短子数组长度
 *
 * @author: caoyanan
 * @time: 2021/5/19 11:20 上午
 */
public class Question01_MinSubArrayForOrdered {

    public static void main(String[] args) {

        int count = 10000;
        for (int i = 0; i < count; i++) {
            int[] arrays = LogarithmInputGenerator.getInstance()
                    .generateRandomArray(10, 20);
            int[] results = minSubArrayForOrdered(arrays);

            if (results.length < arrays.length) {
                System.out.printf("输入: %s, 答案: %s \r\n", Arrays.toString(arrays), Arrays.toString(results));
            }
        }

    }

    /**
     * 思路：
     *  找出右半部分不需要排序的，从左到右遍历，记录最大值Max左，
     *      如果arr[i]比最大值小，记录一个❌，
     *      如果arr[i]比最大值还大，记录一个✔️，并更新最大值。最后取最右侧的❎，rightErrorIndex
     *  找出左半部分不需要排序的，做右往左遍历，记录最小值Min右。
     *      如果arr[i]比最小值大，记录❌
     *      如果arr[i]比最小值还小，记录一个✅，并更新最小值。最后取最左侧的❌， leftErrorIndex;
     *  最后的答案就是 arr[leftErrorIndex... rightErrorIndex]需要排序。
     *
     *  记录左侧最大值，并且越往右，依次增大，这是正常的，就该越来越大，更新最大值，标记对号，如果变小了，那变小的位置一定需要排序
     *  记录右侧最小值，并且越往左，就该越来越小，最小值依次更新，标记对号。如果变大了，这个位置一定要排。
     * @param input
     * @return
     */
    private static int[] minSubArrayForOrdered(int[] input) {

        if (input.length <= 1) {
            return new int[0];
        }
        int maxLeftValue = input[0];
        int rightErrorIndex = 0;
        for (int i = 1; i < input.length; i++) {
            if (input[i] >= maxLeftValue) {
                maxLeftValue = input[i];
            } else {
                rightErrorIndex = i;
            }
        }

        int minRightValue = input[input.length-1];
        int leftErrorIndex = input.length-1;
        for (int i = input.length - 1; i >= 0; i--) {
            if (input[i] <= minRightValue) {
                minRightValue = input[i];
            } else {
                leftErrorIndex = i;
            }
        }
        if (leftErrorIndex >= rightErrorIndex) {
            return new int[0];
        }

        int resultLength = rightErrorIndex - leftErrorIndex + 1;
        int[] result = new int[resultLength];
        System.arraycopy(input, leftErrorIndex, result, 0, resultLength);
        return result;
    }
}
